/**
 * 快速排序算法，复杂度：O(N x N)
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        quickSort(arr, 0, arr.length - 1);

        for (int i : arr) {
            System.out.print(i + ",");
        }
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }

        int midVal = arr[left];
        int i = left;
        int j = right;
        while (i != j) {
            while (arr[j] >= midVal && i < j) {
                j--;
            }
            if (i < j) {
                arr[i] = arr[j];
            }
            while (arr[i] <= midVal && i < j) {
                i++;
            }
            if (i < j) {
                arr[j] = arr[i];
            }
        }
        arr[i] = midVal;

        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }
}
